package dp;

import java.util.ArrayList;
import java.util.List;

public class P131 {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backTrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backTrack(String s, int start, List<String> savedList, List<List<String>> result) {
        if (start == s.length() && checkValid(savedList)) {//结束
            result.add(new ArrayList<>(savedList));
        } else {
            for (int i = start; i < s.length(); i++) {
                String sub = s.substring(start, i + 1);
                savedList.add(sub);
                backTrack(s, i + 1, savedList, result);
                savedList.remove(savedList.size() - 1);
            }
        }

    }

    private boolean checkValid(List<String> valid) {
        for (String s : valid) {
            int l = 0, r = s.length() - 1;
            while (l < r) {
                if (s.charAt(l) != s.charAt(r)) {
                    return false;
                }
                l++;
                r--;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "aab";
        List<List<String>> result = new P131().partition(s);
        for (List<String> r : result) {
            System.out.println(r);
        }
    }
}
